﻿#define _CRT_SECURE_NO_WARNINGS

//给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
//示例 1：
//输入：nums = [1, 2, 3, 1]
//输出：true
//示例 2：
//输入：nums = [1, 2, 3, 4]
//输出：false
//示例 3：
//输入：nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
//输出：true


int cmp(int* e1, int* e2)
{
    return *e1 - *e2;
}

bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize - 1; i++)
    {
        if (nums[i] == nums[i + 1])
        {
            return true;
        }
    }
    return false;
}

//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//子数组 是数组中的一个连续部分。
//示例 1：
//输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
//输出：6
//解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6 。
//示例 2：
//输入：nums = [1]
//输出：1
//示例 3：
//输入：nums = [5, 4, -1, 7, 8]
//输出：23


int maxSubArray(int* nums, int numsSize) {
    int prevsum = 0;
    int maxsum = nums[0];
    for (int i = 0; i < numsSize; i++)
    {
        if (prevsum < 0)
            prevsum = 0;
        int tmp = nums[i];
        if (tmp + prevsum > maxsum)
        {
            maxsum = tmp + prevsum;
        }
        prevsum += tmp;
    }
    return maxsum;
}

//二分查找

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    if (numsSize == 1 && nums[0] == target)
    {
        return 0;
    }
    return -1;
}


//复制带随机指针的链表
struct Node* copyRandomList(struct Node* head)
{

    struct Node* cur = head;
    while (cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        newnode->next = cur->next;
        cur->next = newnode;
        cur = newnode->next;
    }

    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = next;
    }

    cur = head;
    struct Node* newhead = NULL;
    struct Node* newtail = NULL;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (newhead == NULL)
        {
            newhead = newtail = copy;
        }
        else
        {
            newtail->next = copy;
            newtail = newtail->next;
        }
        cur->next = next;
        cur = next;
    }

    return newhead;
}
